package com.cango.student.algorithm.leetcode;

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Stack;

/**
 * leetcode 20 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 * <p>
 * 有效字符串需满足：
 * <p>
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 注意空字符串可被认为是有效字符串。
 */
public class IsValid {
    private HashMap<Character, Character> mappings;

    public IsValid() {
        mappings = new HashMap<>();
        mappings.put(')', '(');
        mappings.put('}', '{');
        mappings.put(']', '[');
    }

    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);

            if (mappings.containsKey(c)) {
                char top = stack.empty() ? '#' : stack.pop();
                if (top != mappings.get(c)) {
                    return false;
                }
            } else {
                stack.push(c);
            }
        }

        return stack.empty();

    }

    public static void main(String[] args) {
        // 新，旧
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> {
            System.out.println(a + " " + b);
            System.out.println(b.compareTo(a));
            // 1在后，负数在前
            return b.compareTo(a);
        });
        queue.offer(1);
        queue.offer(2);
        System.out.println(queue.poll());
        System.out.println(queue.poll());
    }
}
